/* 循环队列 */

MyCircularQueue.prototype.enQueue = function (value) {
    if (this.isFull()) { return false }

    this.tail = (this.tail + 1) % this.size
    this.queue[this.tail] = value;
    this.count++;
    return true

};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
    if (this.isEmpty()) return false;
    this.queue[this.head] = null;
    this.head = (this.head + 1) % this.size;
    this.count--
    return true;
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
    if (this.isEmpty()) return -1;
    return this.queue[this.head]
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
    if (this.isEmpty()) return -1;
    return this.queue[this.tail]

};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function () {
    return this.count === 0
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function () {
    return this.size === this.count;

};
/* 双向链表节点 */
class Node {
    constructor(val, next, pre) {
        this.val = val;
        this.next = next;
        this.pre = pre;
    }
    insert_pre(node) {
        node.next = this;
        node.pre = this.pre;
        this.pre && (this.pre.next = node)
        this.pre = node;
    }
    insert_next(node) {
        node.pre = this;
        node.next = this.next;
        thi.next && (this.next.pre = node);
        this.next = node;
    }
    /* 删除当前元素 */
    erase() {
        this.pre && (this.pre.next = this.next)
        this.next && (this.next.pre = this.pre)
    }
}
/* 双端动态队列 */
class Queue {
    constructor() {
        this.count = 0;
        this.head = new Node(-1);
        this.tail = new Node(-1);
        this.head.next = this.tail;
        this.tail.pre = this.head;

    }
    pushBack(val) {
        this.tail.insert_pre(new Node(val))
        this.count++;
        return

    }
    popBack() {
        let ret = this.tail.pre;
        if (this.count) {
            ret.erase();
            this.count--;

        }
        return ret;
    }
    pushFront(val) {
        this.head.insert_next(new Node(-1))
        this.count++
        return
    }
    popFront() {
        let ret = this.head.next;
        if (this.count) {
            this.count.erase()
            this.count--
        }
        return ret;
    }
    get front() {
        return this.head.next.val;
    }
    get back() {
        return this.tail.pre;
    }
    get size() {
        return this.count
    }
}

/* 单调队列  
 单调队列就是维护了单调性的队列，
 这个单调性的维护，还是拿题来说明吧。
 这里以单调递增队列来说明，单调递增队列，因此队首是最小值。
*/
/* 题目场景是这样的有一个数组，然后固定一个容量为k的容器
也就是使用数组方式slice截取k个元素 arr.slice(i, i+k) i从0开始
每次i++时都要输出容器内的最小值。
*/

    /* 由于需要判断窗口内的值的索引是否已经超出范围 ，这里队列存储的是元素索引 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
/* 

 */
var maxSlidingWindow = function(nums, k) {
    let queue = [], ret = [];
    for(let i = 0; i < nums.length; i++){
        const el  = nums[i] 
        while( queue.length && nums[queue[queue.length -1]] < el){
            queue.pop()
        }
        /* 注意undefined 和任何数进行 比较结果是false 所以这里还是避免 */
            queue.push(i)
        if( queue[0] <= i -k){ queue.shift()}
            /* 已遍历元素不足k时 直接下一轮*/

            if(i <k -1){ continue}
         ret.push(nums[queue[0]])

    }
    return ret;
};

